class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        f[0] = 0;
        g[0] = 0;
        
        int fMax = Integer.MIN_VALUE;
        int gMin = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 1; i <= n; i++) {
            f[i] = Math.max(nums[i-1], f[i-1] + nums[i-1]);
            fMax = Math.max(fMax, f[i]);
            g[i] = Math.min(nums[i-1], g[i-1]+nums[i-1]);
            gMin = Math.min(gMin, g[i]);
            sum += nums[i-1];
        }   
        if(sum == gMin) {
            return fMax;
        }
        return Math.max(fMax, sum-gMin);
    }

    public int maxProduct(int[] nums) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        f[0] = 1;
        g[0] = 1;

        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            int x = nums[i-1], y = f[i-1] * nums[i-1], z = g[i-1] * nums[i-1];
            f[i] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }
}